package binary_tree

func NearestMeeting(root *Node, p1 *Node, p2 *Node) *Node {
	if root == nil || p1 == nil || p2 == nil {return nil}
	leftNode := NearestMeeting(root.Left, p1, p2)
	rightNode := NearestMeeting(root.Right, p1, p2)
	if root == p1 {
		return p1
	}
	if root == p2 {
		return p2
	}
	if leftNode != nil && rightNode != nil {
		return root
	} else if leftNode != nil && rightNode == nil{
		return leftNode
	} else if leftNode == nil && rightNode != nil{
		return rightNode
	}
	return nil
}

func NearestMeeting1(root *Node, p1 *Node, p2 *Node) *Node {
	if root == nil || p1 == nil || p2 == nil {return nil}
	parentMap := map[*Node]*Node{}
	parentMap[root] = nil
	fillParentMap(root, parentMap)
	parentSet := map[*Node]bool{}
	cur := p1
	for cur != nil {
		cur = parentMap[cur]
		parentSet[cur] = true
	}
	cur = p2
	for cur != nil {
		cur = parentMap[cur]
		if parentSet[cur] {
			return cur
		}
	}
	return nil
}

func fillParentMap(root *Node, parentMap map[*Node]*Node) {
	if root == nil {return}
	parentMap[root.Left] = root
	parentMap[root.Right] = root
	fillParentMap(root.Left, parentMap)
	fillParentMap(root.Right, parentMap)
}


func NearestMeeting2(root *Node, p1 *Node, p2 *Node) *Node {
	if root == nil || p1 == nil || p2 == nil {return nil}
	return NearestProcess(root, p1, p2).MeetingN
}

type MeetingInfo struct {
	MeetingN *Node
	IsFindP1 bool
	IsFindP2 bool
}

func NearestProcess(node *Node, p1 *Node, p2 *Node) MeetingInfo {
	if node == nil {
		return MeetingInfo{nil, false, false}
	}
	leftInfo := NearestProcess(node.Left, p1, p2)
	rightInfo := NearestProcess(node.Right, p1, p2)

	var isFindP1, isFindP2 bool
	var findNode *Node
	if node == p1 || leftInfo.IsFindP1 || rightInfo.IsFindP1 {
		isFindP1 = true
	}
	if node == p2 || leftInfo.IsFindP2 || rightInfo.IsFindP2 {
		isFindP2 = true
	}
	if leftInfo.MeetingN != nil {
		findNode = leftInfo.MeetingN
	}
	if rightInfo.MeetingN != nil {
		findNode = rightInfo.MeetingN
	}
	if findNode == nil {
		if isFindP1 && isFindP2 {
			findNode = node
		}
	}
	return MeetingInfo{findNode, isFindP1, isFindP2}
}
